"""

代码
测试用例
测试结果
测试结果
3097. 或值至少为 K 的最短子数组 II
中等
相关标签
premium lock icon
相关企业
提示
给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 -1 。



示例 1：

输入：nums = [1,2,3], k = 2

输出：1

解释：

子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。

示例 2：

输入：nums = [2,1,8], k = 10

输出：3

解释：

子数组 [2,1,8] 的按位 OR 值为 11 ，所以我们返回 3 。

示例 3：

输入：nums = [1,2], k = 0

输出：1

解释：

子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。



提示：

1 <= nums.length <= 2 * 105
0 <= nums[i] <= 109
0 <= k <= 109
"""
from typing import List


class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = float("inf") #最小
        for x,y in enumerate(nums):
            if y>=k:
                ans = 1
                break
            status = True
            for z in range(x-1,-1,-1):
                #或子集，无意义
                if nums[z]|y == nums[z]:
                    break

                nums[z] = nums[z]|y
                if status and nums[z]>=k:
                    ans = min(ans,x-z+1)
                    status = False #前面已有大于，现在肯定不是最短，只是为了保持前面是父级所以不跳过

        return ans if ans != float("inf") else -1

if __name__ == '__main__':
    # print(Solution().minimumSubarrayLength([1,2,3],2))
    print(Solution().minimumSubarrayLength([2,1,8],10)) #3
    print(Solution().minimumSubarrayLength([2,1,9,12],21)) #-1
